#pragma once

#include <algorithm>




namespace boostext
{
	/**
	 * This is the base class for all storage policies that store a sequence of elements in an
	 * STL compliant container.
	 *
	 * It contains necessary typedefs, an instance of the actual container and some functions that should
	 * be fleshed out by an actual storage policy.
	 */
	template <class container>
	class container_base
	{
	public:

		typedef typename container::iterator                  iterator;
		typedef typename container::const_iterator            const_iterator;
		typedef typename container::value_type                value_type;
		typedef typename boost::add_const<value_type>::type   const_value_type;

	private:

		container   m_container;

	protected:

		/**
		 * Create an empty container_storage.
		 */
		container_base()
		{}

		/**
		 * Create a container_storage from a sequence of elements.
		 * It's enough go pass a const_iterator, since this policy makes a copy of the range anyway.
		 */
		container_base(const_iterator begin, const_iterator end)
			: m_container(begin, end)
		{}

	public:

		/**
		 * Get access to the first element in the sequence.
		 */
		iterator begin() { return m_container.begin(); }
		iterator end() { return m_container.end(); }

		/**
		 * Get access to the first element in the sequence.
		 */
		const_iterator begin() const { return m_container.begin(); }
		const_iterator end() const { return m_container.end(); }



		/**
		 * Insert an element into the sequence at the given position.
		 */
		iterator insert(const_iterator where, const_value_type& that) { return m_container.insert(where, that); }

		/**
		 * Erase an element from this sequence.
		 */
		iterator erase(const_iterator where) { return m_container.erase(where); }

		/**
		 * Erase a range of elements from this sequence.
		 */
		iterator erase(const_iterator begin, const_iterator end) { return m_container.erase(begin, end); }

	public:

		/**
		 * Reserves capacity for at least the given number of elements.
		 * This function is only available if the given container supports
		 * reserving capacity.
		 *
		 * @note   this function is implemented as a template function to surpress errors when the container doesn't support reserving
		 */
		template <typename size_t>
		void reserve(size_t numElements)
		{
			m_container.reserve(numElements);
		}
	};
	///////////////////////////////////////////////////////////////////////////////////////////////////




	/**
	 * This is the default storage policy for a sequence resource.
	 * All elements are simply pushed back to the STL-compliant container.
	 */
	template <class cont>
	class container
		: public container_base<cont>
	{
	public:

		enum { totally_ordered = false, ascending = false, descending = false };

	protected:

		/**
		 * Create an empty container.
		 */
		container()
		{}

		/**
		 * Create a container from a sequence of elements.
		 * Makes a copy of the sequence that is stored in the STL-compliant container.
		 */
		template <typename Iter>
		container(Iter begin, Iter end)
			: container_storage(begin, end)
		{}

	public:

		/**
		 * Insert an element into this storage policy.
		 * The element is simply pushed at the end.
		 */
		iterator insert(const_value_type& that)
		{
			return __super::insert(end(), that);
		}
	};
	///////////////////////////////////////////////////////////////////////////////////////////////////



#ifdef blub
	/**
	 * This storage policy requires that the element is totally ordered, so that
	 * the storage can be sorted in ascending order. One must note that this policy
	 * does a sorted insertion, which means that the item is inserted at the right
	 * place from the start.
	 */
	template <typename container>
	class insert_ascending_storage
		: public container_storage_base<container>
	{
	public:

		enum { totally_ordered = true, ascending = true, descending = false };

	protected:

		/**
		 * Create an empty insert_ascending_storage.
		 */
		insert_ascending_storage()
		{}

		/**
		 * Create a insert_ascending_storage from a sequence of elements.
		 * Makes a copy of the given sequence and then sorts them ascending.
		 */
		template <typename Iter>
		insert_ascending_storage(Iter begin, Iter end)
			: container_storage(begin, end)
		{
			std::sort(__super::begin(), __super:.end(), std::less<value_type>());
		}

	public:

		/**
		 * Insert an element into this storage policy.
		 * The element is simply pushed at the end.
		 */
		iterator insert(const_value_type& that)
		{
			iterator i   = begin();
			iterator end = __super::end();

			while(i != end)
				if(that <= *i)
					break;
				else
					++i;

			return __super::insert(i, that);
		}
	};
	///////////////////////////////////////////////////////////////////////////////////////////////////




	/**
	 * This storage policy requires that the element is totally ordered, so that
	 * the storage can be sorted in descending order. One must note that this policy
	 * does a sorted insertion, which means that the item is inserted at the right
	 * place from the start.
	 */
	template <typename container>
	class insert_descending_storage
		: public container_storage_base<container>
	{
	public:

		enum { totally_ordered = true, ascending = false, descending = true };

	protected:

		/**
		 * Create an empty insert_descending_storage.
		 */
		insert_descending_storage()
		{}

		/**
		 * Create a insert_descending_storage from a sequence of elements.
		 * Makes a copy of the given sequence and sorts it descending.
		 */
		template <typename Iter>
		insert_descending_storage(Iter begin, Iter end)
			: container_storage_base(begin, end)
		{
			std::sort(__super::begin(), __super::end(), std::greater<value_type>());
		}

	public:

		/**
		 * Insert an element into this storage policy.
		 * The element is simply pushed at the end.
		 */
		iterator insert(const_value_type& that)
		{
			iterator i   = begin();
			iterator end = __super::end();

			while(i != end)
				if(that >= *i)
					break;
				else
					++i;

			return __super::insert(i, that);
		}
	};
	///////////////////////////////////////////////////////////////////////////////////////////////////
#endif


	template <typename T>
	class c_array
	{
	public:

		typedef T                                             value_type;
		typedef typename boost::add_const<value_type>::type   const_value_type;

		typedef value_type*                                   iterator;
		typedef const_value_type*                             const_iterator;

		private:

		iterator   m_begin;
		iterator   m_end;

	private:

		/**
		 * The c_array does not have a default constructor, because it
		 * only stores iterators to an already existing sequence of elements.
		 */
		c_array();

	public:

		/**
		 * Create a c_array from a sequence of elements.
		 * It's important to pass a mutable iterator, otherwise the elements
		 * may not be modified through this storage.
		 */
		c_array(iterator begin, iterator end)
			: m_begin(begin)
			, m_end(end)
		{}



		iterator begin() { return m_begin; }
		iterator end() { return m_end; }

		const_iterator begin() const { return m_begin; }
		const_iterator end() const { return m_end; }
	};
	///////////////////////////////////////////////////////////////////////////////////////////////




	/**
	 * This storage policy does not keep the actual container, but only stores iterators
	 * to the sequence of elements of another storage.
	 */
	template <typename iterator, typename const_iterator>
	class iterator_storage
	{
	public:

		typedef iterator         iterator;
		typedef const_iterator   const_iterator;

	private:

		iterator   m_begin;
		iterator   m_end;

	private:

		/**
		 * The iterator_storage does not have a default constructor, because it
		 * only stores iterators to an already existing sequence of elements.
		 */
		iterator_storage();

	protected:

		/**
		 * Create an iterator_storage from a sequence of elements.
		 * It's important to pass a mutable iterator, otherwise the elements
		 * may not be modified through this storage.
		 */
		iterator_storage(iterator begin, iterator end)
			: m_begin(begin)
			, m_end(end)
		{}



		iterator storage_begin() { return m_begin; }
		iterator storage_end() { return m_end; }

		const_iterator storage_begin() const { return m_begin; }
		const_iterator storage_end() const { return m_end; }
	};
	///////////////////////////////////////////////////////////////////////////////////////////////
}
///////////////////////////////////////////////////////////////////////////////////////////////////
